package dp;

public class _23_122_买卖股票的最佳时机Ⅲ {
    public int maxProfit(int[] prices) {

    	int dp[][] = new int[prices.length][5];
    	dp[0][1] = -prices[0]; // 第一次持有
    	dp[0][2] = 0; // 第一次不持有
    	dp[0][3] = -prices[0]; // 第二次持有
    	dp[0][4] = 0; // 第二次不持有
    	
    	for(int i = 1; i < prices.length; i++) {
    		// 第一次持有 前一天持有的金额 今天持有的金额
    		dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
    		// 第一次不持有 前一天不持有的金额 今天不持有的金额(将前一天的持有售除
    		dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
    		// 第二次持有 前一天持有的金额 第一次不持有的利润-今天持有的金额
    		dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
    		// 第二次不持有 前一天不持有的金额 今天不持有的金额(将前一天的持有售出 这里包含了第一次持有的利润+第二次持有的利润
    		dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);
    	}

//    	for(int i = 0; i < prices.length; i++) {
//    		System.out.println("i:" + i + " " + dp[i][1] + " " + dp[i][2] + " " + dp[i][3] + " " + dp[i][4]);
//    	}
    	return dp[prices.length-1][4];
    }
    public static void main(String[] args) {
    	int prices[] = {7,6,4,3,1};
		System.out.println(new _23_122_买卖股票的最佳时机Ⅲ().maxProfit(prices));
	}
}
